Broadcasting is inherent to wireless communications. Any receiver operating within range of a transmission may be able to listen to the transmission and may be able to decode at least a portion of the transmission. The broadcast nature of wireless communications may be exploited to allow simultaneous transmissions to several receivers at high rates. However, eavesdropping may also become easier.
Cryptography is a traditional approach to protect transmissions against eavesdropping. In general, there are two different types of cryptographic systems: secret key cryptosystems and public-key cryptosystems. Secret key cryptosystems require a secret key shared between a sender and a receiver. Public-key cryptosystems do not require the pre-establishment of a secret key, but may be more susceptible to advanced attacks, such as man-in-the-middle attack. Both types of cryptosystems may be based on an assumption that the eavesdropper has limited computational power. For example, in the well-known RSA public-key cryptosystem, the security is based on the computational complexity involved in factoring large integers, while many other cryptosystems are based on the difficulty of computing discrete logarithms in certain groups. Therefore, traditional cryptosystems lack absolute security since given enough time and computation power, they may be broken.
FIG. 1 illustrates a prior art cipher system 100. Cipher system 100 may be illustrative of a Shannon cipher system. Shannon defined a secrecy system to be perfectly secret if the cipher text is statistically independent of the message. Perfect secrecy is the strongest notion of security since observing the cipher text does not reveal any information regarding the message. In cipher system 100, assumptions include: 1) transmitter 105 and receiver 110 share a secret key that is unknown to eavesdropper 115; 2) transmission of the message is noiseless to both receiver 110 and eavesdropper 115. Under these assumptions, cipher system 100 may be shown to have perfect secrecy if the length of the secret key is at least as long as that of the message.
Shannon's result on perfect secrecy systems presents is pessimistic. It has been shown that Shannon's pessimistic result is not due to the strong notion of information-theoretic security, but is a result of the assumption that the transmission of the message occur over noiseless channels. By extending the Shannon cipher system to a noisy setting, it may be possible to design cipher systems that can deliver a message reliably to a receiver while keeping it asymptotically perfectly secret from an eavesdropper without the need for a secret key shared initially.
In fact, it has been shown that if the transmitter and the receiver can observe a common noisy channel, they may exploit the inherent noisiness of a channel to generate a secret key that may be used to encrypt messages sent over the channel. Furthermore, if the transmitter and the receiver can communicate over an error-free public channel (herein referred to as public communications), they can generate the same secret keys with high probability. However, when communicating over a public channel, no significant knowledge about the secret key may be revealed. In other words, obtaining publicly communicated information must not provide the eavesdropper knowledge about the secret key.